package LinkedList;

/**
 * 题目 ：相交链表
 * 题目具体描述 ：
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 */
public class P160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
         *  思路 ：即，将两条链表长度不一致的链表，化为长度一致的两条链表（需要对于链表进行遍历，从而获取链表的长度）
         */
        ListNode node1 = headA;
        ListNode node2 = headB;
        Integer lengthA = 0;
        Integer lengthB = 0;
        while(node1 != null){
            lengthA++;
            node1 = node1.next;
        }
        while(node2 != null){
            lengthB++;
            node2 = node2.next;
        }
        Integer length = Math.abs(lengthA - lengthB);
        if(lengthA - lengthB >= 0){
            for (Integer i = 0; i < length; i++) {
                headA = headA.next;
            }
        }
        else {
            for (Integer i = 0; i < length; i++) {
                headB = headB.next;
            }
        }
        while(headA != null && headB != null){
            if(headA == headB){  // 节点相同，并不是节点的值相同
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}
